package main

// persons 中的 0 1 编号代表有几个候选人，0 是标号为 0的候选人
// times 就是一个时刻表。time第 i索引位置时，对应的时间为 times[i], 此时为 persons[i]位置的候选人投票
// 比较规则：（示例中解释还是清晰的）
// 也就是说， t 对应的是一个 时刻，在 t时刻之前， 观察 persons数组， 候选人当中票数最高的就赢
// 如果存在票数一样的话， 那最后一个得到投票的赢，处于领先

// 因为 Q方法 需要被调用的次数达到了 10^4!! 这个数量级，O(n) 和 O(logn) 才能考虑
// 按照官方的题解方法，先预处理 + 二分查找。  求出每个时间的获胜者，保存进数组
// 再二分查找该数组，应对 10^4 规模的调用 Q方法，查找 获胜者！
type TopVotedCandidate struct {
	tops, times []int
}

func Constructor(persons, times []int) TopVotedCandidate {
	// 1. 记录每个时间。谁的票数最多
	tops := []int{}
	// top 当前遍历位置，最大的person
	top := -1
	// 用来统计，计数
	voteCounts := map[int]int{-1: -1}
	for _, p := range persons {
		voteCounts[p]++
		// 连大小带时间比对，都在里面了
		if voteCounts[p] >= voteCounts[top] {
			top = p
		}
		tops = append(tops, top)
	}
	// 返回初始化的结构体对象
	return TopVotedCandidate{tops, times}
}

// 通过二分查找，谁的票数最多。
func (c *TopVotedCandidate) Q(t int) int {
	// return c.tops[sort.SearchInts(c.times, t+1)-1], 内置二分
	// 手写二分: 找到最接近当前元素（<=）
	i, j := 0, len(c.times) - 1
	for i < j {
		// 避免i+j 大于 int32的写法， 注意 + 1，避免死循环
		mid := i + (j - i + 1) / 2
		if c.times[mid] <= t {
			i = mid
		} else {
			j = mid - 1
		}
	}
	return c.tops[i]
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * obj := Constructor(persons, times);
 * param_1 := obj.Q(t);
 */

